package com.walterlife.sort;

public class QuickSort {

    public static void sort(int[] arr, int low, int high) {
        if(arr == null || arr.length == 0 || low < 0 || high < 0 || high < low) {
            return;
        } 

        int mid = low;
        // 默认第一个数为坑
        int pivot = arr[mid];
        int lidx = low, hidx = high;
        while(lidx < hidx) {
            // 往右边找小于pivot 的数 填坑
            while(lidx < hidx && arr[hidx] >= pivot) {
                hidx--;
            } 
            // 找到则填第一坑，空出来的坑，往左边找数填坑
            if(lidx < hidx) {
                arr[lidx++] = arr[hidx];
            } 

            while(lidx < hidx && arr[lidx] < pivot) {
                lidx++;
            } 
            // 找到则填坑
            if(lidx < hidx) {
                arr[hidx--] = arr[lidx];
            } 
        }
        // 将基准书填到最后一个坑上
        arr[lidx] = pivot;

        // 对左边的数进行同等的操作
        sort(arr, low, lidx-1);
        // 对又边的数进行同等的操作
        sort(arr, lidx+1, high);
    } 
}
